# 174. 付账问题
# https://www.lanqiao.cn/problems/174/learning/?page=1&first_category_id=1&second_category_id=3
# Date: 2025/2/15
import math


def payment_standard_deviation(bill_num: int, arr):  # 1 2 3 4 -> 10
    n = len(arr)
    avg = bill_num / n
    arr.sort()
    s = 0
    for i in range(n):
        if arr[i] <= bill_num / (n - i):
            bill_num -= arr[i]  # 穷哥们把兜里的钱都拿出来
            s += (arr[i] - avg) ** 2  # 累计平方差用于后续计算标准差
        else:
            rich_avg = bill_num / (n - i)  # 富哥们要掏钱的平均值
            s += ((rich_avg - avg) ** 2) * (n - i)  # 累计平方差用于后续计算标准差
            return format(math.sqrt(s / n), '.4f')


def payment_standard_deviation_wrong(bill_num: int, arr):
    """这是一个错误的写法, 与正确写法的区别在于:
    正确函数判断 arr[i] <= bill_num/(n-i)（动态剩余平均值）
    错误函数判断 arr[i] <= avg（静态总平均值）
    主要的问题在于, 如果使用静态均值来区分穷哥们和富哥们, 那么一些富哥们中比较穷的可能付不起富哥们要掏钱的平均值
    例如: 10,20,30,40 -> 100 也就是每个人要把所有的钱都用于付账单的情况
    在静态均值的情况下: avg = 25
    i=0：10<=25→是。支付10，剩余90.
    i=1：20<=25→是。支付20，剩余70.
    i=2：30>25→进入else。此时，rich_avg=70/(2)=35, 也就是要付35, 但是这个富哥们只有30元, 所以错误
    """
    n = len(arr)
    avg = bill_num / n
    arr.sort()
    s = 0
    for i in range(n):
        if arr[i] <= avg:
            bill_num -= arr[i]
            s += (arr[i] - avg) ** 2
        else:
            rich_avg = bill_num / (n - i)
            s += ((rich_avg - avg) ** 2) * (n - i)
            return format(math.sqrt(s / n), '.4f')  # 四舍五入保留4为小数


if __name__ == '__main__':
    print(payment_standard_deviation(2333, [666, 666, 666, 666, 666]))  # 0
    print(payment_standard_deviation(5, [0, 1, 2, 3, 4]))
    print(payment_standard_deviation(20, [0, 2, 3, 16, 18]))
    with open("../data/174.in", "r") as file:
        n, k = map(int, file.readline().split())
        inp = list(map(int, file.readline().split()))
    print(payment_standard_deviation(k, inp))  # 31502131.8675
